package org.liaohailong.victor;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * Author: liaohailong
 * Date: 2025/2/24
 * Time: 16:16
 * Description:
 **/
public class TreeStudy {

    public static Node create(int[] arr) {

        LinkedList<Node> list = new LinkedList<>();
        for (int value : arr) list.add(new Node(value));

        Node root = list.removeFirst();

        LinkedList<Node> parents = new LinkedList<>();
        parents.add(root);

        addNode(parents, list);

        return root;
    }

    private static void addNode(LinkedList<Node> parents, LinkedList<Node> list) {
        if (parents.isEmpty()) return;

        LinkedList<Node> nodes = new LinkedList<>();

        for (Node node : parents) {

            if (!list.isEmpty()) {
                node.left = list.removeFirst();
                nodes.add(node.left);
            } else break;

            if (!list.isEmpty()) {
                node.right = list.removeFirst();
                nodes.add(node.right);
            } else break;
        }

        parents.clear();
        parents.addAll(nodes);

        addNode(parents, list);
    }

    public static ArrayList<Integer> print(Node root) {

        ArrayList<Integer> result = new ArrayList<>();

        LinkedList<Node> bfs = new LinkedList<>();
        bfs.add(root);

        int count = bfs.size();
        while (count > 0) {

            for (int i = 0; i < count; i++) {
                Node node = bfs.removeFirst();
                result.add(node.value);

                if (node.left != null)
                    bfs.add(node.left);
                if (node.right != null)
                    bfs.add(node.right);
            }

            count = bfs.size();
        }

        return result;
    }

    public static void traversal(Node node) {

        if (node.left != null) traversal(node.left);
        if (node.right != null) traversal(node.right);

        System.out.println(node.value);
    }

    public static void traversal2(Node node) {

        Stack<Node> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {

            Node pop = stack.pop();

            if (pop.left != null) stack.push(pop.left);
            if (pop.right != null) stack.push(pop.right);

            System.out.println(pop.value);
        }
    }


    public static final class Node {
        public Node left;
        public Node right;
        public final int value;

        public Node(int value) {
            this.value = value;
        }
    }
}
